//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 
//
// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 示例: 
//
// 输入: 4
//输出: [
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
//解释: 4 皇后问题存在两个不同的解法。
// 
// Related Topics 回溯算法


package com.gule.gl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class NQueens {
    /**
     * 51N皇后
     *
     * @param args
     * @link
     */
    public static void main(String[] args) {
        Solution solution = new NQueens().new Solution();
        System.out.println(solution.solveNQueens(4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<String>> resList;

        public List<List<String>> solveNQueens(int n) {
            resList = new ArrayList<>();
            backTracking(n, 0, new int[n]);
            return resList;
        }

        private void backTracking(int n, int row, int[] columns) {
            //判断是否在所有n行里面放好的皇后，如果是则说明发现了一种放置的方法
            if (row == n) {
                buildResList(row, columns);
                return;
            }
            //尝试将皇后放在当前行的每一列
            for (int col = 0; col < n; col++) {
                //push
                columns[row] = col;
                if (check(row, col, columns)) {
                    backTracking(n, row + 1, columns);
                }
                //pop
                columns[row] = -1;
            }
        }

        /**
         * 构建返回的list
         *
         * @param row
         * @param columns
         */
        private void buildResList(int row, int[] columns) {
            List<String> ss = new ArrayList<>();
            for (int i = 0; i < row; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < row; j++) {

                    if (columns[i] == j) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                ss.add(sb.toString());
            }
            resList.add(ss);
        }

        /**
         * @param row    行
         * @param col    列
         * @param cloums 列的数组
         * @return boolean
         */
        private boolean check(int row, int col, int[] cloums) {
            for (int r = 0; r < row; r++) {
                if (cloums[r] == col || row - r == Math.abs(cloums[r] - col)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
